PR é a classe de complexidade de todas as funções recursivas primitivas , ou, equivalentemente, o conjunto de todas as linguagens formais que pode ser decididas por uma tal função. Isso inclui a adição, multiplicação, potência, tetração, etc.

A função de Ackermann é um exemplo de função que não é recursiva primitiva, mostrando que PR esta estritamente contida em R (Cooper, 2004:88).

Por outro lado, podemos "enumerar" qualquer conjunto recursivamente enumerável (veja também a sua classe de complexidade RE) por uma função recursiva primitiva no seguinte sentido: dada uma entrada (M, k), onde M é uma máquina de Turing e k é um número inteiro, se M pára dentro de k passos, dê M como saída; caso contrário, dê nada como saída. Então, a união das saídas, através de todas as entradas possíveis (M, k), é exatamente o conjunto das M que param.

PR estritamente contém ELEMENTAR.